package com.zk.algorithm.stackandqueue;

import com.zk.algorithm.annotation.JianZhiOffer;
import com.zk.algorithm.annotation.LeetCode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 两个栈 A 和 B
 * - push 永远往 A push
 * - pop A 元素不为空，全部转移至 B，然后 pop B
 * - peek A 元素不为空，全部转移至 B，然后 peek B
 *
 * @author zk
 */
@JianZhiOffer
@LeetCode("232")
public class ImplementQueueUsingStacks {

    Deque<Integer> stackA = new ArrayDeque<Integer>();
    Deque<Integer> stackB = new ArrayDeque<Integer>();

    /** Initialize your data structure here. */
    public ImplementQueueUsingStacks() {
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stackA.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!stackB.isEmpty()) {
            return stackB.pop();
        }

        while (!stackA.isEmpty()) {
            stackB.push(stackA.pop());
        }

        return stackB.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (!stackB.isEmpty()) {
            return stackB.peek();
        }

        while (!stackA.isEmpty()) {
            stackB.push(stackA.pop());
        }

        return stackB.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stackA.isEmpty() && stackB.isEmpty();
    }

}
